package cn.mayday.algorithms.year2021.month1.B海量数据专题;

import java.util.HashMap;
import java.util.Map;

/**
 * 如何从大量数据中找出高频词？
 *
 * @author Mayday05
 * @date 2021/5/13 16:43
 */
public class Top100Words {

//    https://github.com/doocs/advanced-java/blob/main/docs/big-data/find-top-100-words.md

//    题目描述
//    有一个 1GB 大小的文件，文件里每一行是一个词，每个词的大小不超过 16B，内存大小限制是 1MB，要求返回频数最高的 100 个词(Top 100)。
//
//    解答思路
//    由于内存限制，我们依然无法直接将大文件的所有词一次读到内存中。因此，同样可以采用分治策略，把一个大文件分解成多个小文件，保证每个文件的大小小于 1MB，进而直接将单个小文件读取到内存中进行处理。
//
//    思路如下：
//
//    首先遍历大文件，对遍历到的每个词 x，执行 hash(x) % 5000 ，将结果为 i 的词存放到文件 ai 中。遍历结束后，我们可以得到 5000 个小文件。每个小文件的大小为 200KB 左右。如果有的小文件大小仍然超过 1MB，则采用同样的方式继续进行分解。
//
//    接着统计每个小文件中出现频数最高的 100 个词。最简单的方式是使用 HashMap 来实现。其中 key 为词，value 为该词出现的频率。具体方法是：对于遍历到的词 x，如果在 map 中不存在，则执行 map.put(x, 1) ；若存在，则执行 map.put(x, map.get(x)+1) ，将该词频数加 1。
//
//    上面我们统计了每个小文件单词出现的频数。接下来，我们可以通过维护一个小顶堆来找出所有词中出现频数最高的 100 个。具体方法是：依次遍历每个小文件，构建一个小顶堆，堆大小为 100。如果遍历到的词的出现次数大于堆顶词的出现次数，则用新词替换堆顶的词，然后重新调整为小顶堆，遍历结束后，小顶堆上的词就是出现频数最高的 100 个词。
//
//    方法总结
//    分而治之，进行哈希取余；
//    使用 HashMap 统计频数；
//    求解最大的 TopN 个，用小顶堆；求解最小的 TopN 个，用大顶堆。


    // 伪代码

    private static Node[] heap;

    public static void main(String[] args) {
        // 1.将日志文件拆分成一系列小文件（每个文件小于512M），且按照url的hash值进行拆分保证
        // 同一个url放到同一个小文件中
        String[] paths = splitBigFileToSmall("path/of/big/file");

        // 2.构造一个包含10个节点的小顶堆，节点包含url以及出现的次数
        heap = new Node[10];

        // 3.统计每一个小文件中url出现的次数，放入到map中，统计完一个遍历map
        // 将url及出现的次数构造成堆的节点插入小顶堆中
        for (String path : paths) {
            Map<String, Long> map = getNumOfPerUrlAndPutIntoHeap(path, heap);
        }

        // 4.统计完所有的小文件最终生成的小顶堆中存放的url即为出现次数最多的十个url
        for (Node node : heap) {
            StringBuilder stringBuilder = new StringBuilder();
            stringBuilder.append(node.getUrl());
            stringBuilder.append(":");
            stringBuilder.append(node.getCount());
            System.out.println(stringBuilder.toString());
        }
    }

    /**
     * 将日志文件拆分成一系列小文件（每个文件小于512M），且按照url的hash值进行
     * 拆分保证同一个url放到同一个小文件中
     *
     * @param path 大文件的path
     * @return
     */
    private static String[] splitBigFileToSmall(String path) {
        /**
         * ...
         */
        return new String[3000];
    }

    /**
     * 统计每一个小文件中url出现的次数，放入到map中，统计完一个遍历map将url及
     * 出现的次数构造成堆的节点插入小顶堆中
     *
     * @param filePath
     * @param heap
     * @return
     */
    private static Map<String, Long> getNumOfPerUrlAndPutIntoHeap(String filePath, Node[] heap) {
        /**
         *
         */
        return new HashMap<>();
    }


    public static class Node {
        private String url;

        private long count;

        public String getUrl() {
            return url;
        }

        public long getCount() {
            return count;
        }
    }


}
